package com.leetcode.二分查找;

public class lc_33 {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5};
        int target= 6;
        System.out.println(search(nums, target));
    }

    public static int search(int[] nums, int target) {
        //思路,两次二分法
        int n = nums.length;
        int i = searchMin(nums);
        if (target > nums[n - 1]) {
            return lowerBound(nums, -1, i, target);
        }
        return lowerBound(nums, i - 1, n, target);
    }

    //方法一: 找到旋转数组最小值的下标, 得到两段数组
    private static int searchMin(int[] nums) {
        int n = nums.length;
        int left = -1;
        int right = n - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= nums[n - 1]) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    //方法二:传入分段的子数组, 找出其中是否包含target, 注意这里是开区间
    private static int lowerBound(int[] nums, int left, int right, int target) {
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return nums[right] == target ? right : -1;
    }

}
